#include "skipList.h"


//Constructor
skipList::skipList()
{
	topHead = new skipListItem(0, NULL, NULL);
	height = 1;
}


//Return true if the skip list is empty
bool skipList::empty()
{
	//Create a item that points to the top of the head
	skipListItem* item = topHead;

	//We go down on the head until arrive to the bottom element
	while(item->getDown() != NULL)
	{
		item = item->getDown();
	}

	//If the bottom element has nothing at its right, it means that the list is empty
	if(item->getRight() == NULL) return true;
	else return false;
}


void skipList::allocate(int width, int height)
{}


//Free the memory allocated
void skipList::freeNodes()
{
	skipListItem* headItem = topHead;
	skipListItem* listItem;
	skipListItem* toDelete;

	//We go over each element of the head
	while(headItem != NULL)
	{
		//Obtain the first item of the list at the level of headItem
		listItem = headItem->getRight();

		//We go over each element of the list that starts in headItem
		while(listItem != NULL)
		{
			//Store in listItem the next node and delete the previous listItem
			toDelete = listItem;
			listItem = listItem->getRight();
			delete toDelete;
		}
		
		//Now that we are at the end of the list that starts in headItem, 
		//we should go to the list below and delete the previous headItem
		toDelete = headItem;
		headItem = headItem->getDown();
		delete toDelete;
	}
}


//Remove the node from the skip list and add it to it again keeping the list sorted
void skipList::modifyNode(skipListItem* item)
{
	Node* node = item->getRight()->getNode();

	//Remove the nodes from the skip list
	remove(item);

	//Add the node to the skip list
	addNode(node);
}


//Look for a node with coordinates x, y in the skip list
//If found, returns a pointer to the node and a pointer to the skipListItem in which this pointer is stored
std::pair<skipListItem*, Node*> skipList::findNode(int x, int y)
{
	std::pair<skipListItem*, Node*> p;
	skipListItem* headItem = topHead;
	skipListItem* listItem;

	//We will go over each linked list from top to bottom
	while(headItem != NULL)
	{
		//While there are elements at the right of the current item and the next is less than x,y, we keep moving to the right
		listItem = headItem;
		while(listItem->getRight() != NULL && listItem->getRight()->getNode()->lessThanByXY(x, y))
		{
			listItem = listItem->getRight();
		}

		//If we have not stopped because the next item is null, in other words,
		//if the next element is not less than x,y
		if(listItem->getRight() != NULL)
		{
			//If the next element is not greater than x,y, then we have found it
			if(! listItem->getRight()->getNode()->greaterThanByXY(x, y))
			{
				p.first = listItem;
				p.second = listItem->getRight()->getNode();
				return p;
			}
		}
		
		//We go down to keep looking in the lists below
		headItem = listItem->getDown();	
	}

	p.first = 0;
	p.second = 0;
	return p;
}


//Returns the node with lowest cost in the skip list
Node* skipList::selectNodeLowestScore()
{
	Node* lowestNode = 0;
	skipListItem* lowestItem = 0;

	//We need to go to the bottom list which is the only one that contains all the nodes inserted in the list
	skipListItem* item = topHead;
	while(item->getDown() != NULL)
	{
		item = item->getDown();
	}

	//If there is at least one element in the list
	if(item->getRight() != NULL)
	{
		//Initialise the lowest node with the node of the first element of the list
		lowestNode = item->getRight()->getNode();
		lowestItem = item;

		//Scan every item on the list and store in lowestNode the node with lowest cost
		item = item->getRight();
		while(item->getRight() != NULL)
		{
			//Check if this node has a lower cost
			if( item->getRight()->getNode()->getF() < lowestNode->getF())
			{
				lowestNode = item->getRight()->getNode();
				lowestItem = item;
			}

			//Move to the right
			item = item->getRight();
		}
	}

	//If the list is not empty, we have selected the lowest node and we have to remove it from the list and return it
	if(item) remove((findNode(lowestNode->getX(), lowestNode->getY())).first);
	return lowestNode;
}


//Remove all the items from the column pointed by skipListItem
void skipList::remove(skipListItem* item)
{
	//Obtain the second element of the column, which we have to delete
	skipListItem* toDelete = item->getRight()->getDown();

	//Delete the first element of the column
	skipListItem* aux = item->getRight()->getRight();
	delete item->getRight();
	item->setRight(aux);

	//Scan the lists below to delete the rest of the elements of the column
	item = item->getDown();
	while(item != NULL)
	{
		//Go right on the current list until find the next element of the list to delete
		while(item->getRight() != toDelete)
		{
			//Move to the right
			item = item->getRight();
		}

		//Obtain the next element of the column to delete
		toDelete = toDelete->getDown();

		//Delete that we were looking for
		aux = item->getRight()->getRight();
		delete item->getRight();
		item->setRight(aux);

		//Go down to find and remove the item toDelete
		item = item->getDown();
	}
}


//Add the node to the skip list to a position in which the it remains sorted by X and Y attributes
void skipList::addNode(Node* node)
{
	int i = height - 1;
	skipListItem** pointers = new skipListItem*[height];

	skipListItem* headItem = topHead;
	skipListItem* listItem;

	//We will go over each linked list from top to bottom
	while(headItem != NULL)
	{
		//While there are elements at the right of the current item and the next is less than x,y, we keep moving to the right
		listItem = headItem;
		while(listItem->getRight() != NULL && listItem->getRight()->getNode()->lessThanByXY(node->getX(), node->getY()))
		{
			listItem = listItem->getRight();
		}

		*(pointers + i--) = listItem;
		
		//We go down to keep looking in the lists below
		headItem = listItem->getDown();	
	}
	
	//Create the new item
	skipListItem* newItem = new skipListItem(node, listItem->getRight(), NULL);

	//Link the head with the new element
	listItem->setRight(newItem);
	i += 2;

	//Generate more items with the same node randomly
	skipListItem* aux;
	while(rand() % 2)
	{
		//If this column is higher than the head's column
		if(height - 1 < i)
		{
			//Create the new element
			aux = newItem;
			newItem = new skipListItem(node, NULL, aux);

			//Create a head element and add it to the top of the head's column
			skipListItem* newHead = new skipListItem(0, newItem, topHead);
			topHead = newHead;
			height++;
			i++;
		}
		else
		{
			//Create the new element
			aux = newItem;
			newItem = new skipListItem(node, (*(pointers + i))->getRight(), aux);
			(*(pointers + i))->setRight(newItem);
			i++;
		}
	}

	delete pointers;
}